package 算法shiyan;/**
 * ************************************************************************
 * 项目名称: projectweb <br>
 * 文件名称:  <br>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br>
 * 文件创建：1913040634刘世锦  <br>
 * 创建时间: 2021/5/14 <br>
 *
 * @version v1.0 <br>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br>
 * ************************************************************************
 */

/**
 * @ProjectName: projectweb
 * @ClassName: s
 * @Description: 请描述该类的功能
 * @Author: 1913040634刘世锦
 * @Date: 2021/5/14 20:47 .
 * @version v1.0
 */


import java.util.Scanner;

public class TSP {
    public static void main(String[] args) {
        //输入城市个数
        System.out.println("输入城市个数");
        int n;
        final int MAX = 1000000000;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        //存储各城市之间的距离
        System.out.println("各城市之间的距离");
        int[][] sd = new int[n][n];
        //用于存储距离
        int[] sq = new int[n];
        //用于表示sq已存的距离
        int top = 0;
        //用于表示该城市是否已经走过了(1表示已走，0表示未走过)
        int[] flag = new int[n];
        //为sq赋值
        for (int i = 0; i < n; i++) {
            sq[i] = MAX;
        }
        //构造城市距离的矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sd[i][j] = sc.nextInt();
            }
        }

        //输入城市的起点(城市从1开始算，但数组构造的时候是从0开始的，因此还需要start-1)
        System.out.println("城市的起始位置");
        int start = sc.nextInt();
        System.out.print(start+"->");
        start = start-1;
        //记录起点城市，避免走到最后的时候无法找到起点了
        int firstCity = start;
        //记录下一个城市
        int nextCity = -1;
        //记录该城市是否已经被访问了，若已访问则为1，为访问则为0
        flag[start] = 1;
        //五个城市中，单项走不考虑回到起点的话，只有四条路
        //当sq已保存第四条路（也就是sq下标为n-2时）的距离的时候，退出循环，此时已走遍所有城市
        while (sq[n-2]==MAX) {//此处也可写top<n-1
            //遍历该城市与其他各个城市的距离
            for (int j = 0; j < n; j++) {
                //寻找出与该城市距离最小的邻接城市，且该城市未去过(如果输入为0则表示两条路不相通)
                if (sq[top] > sd[start][j] && flag[j] == 0&&sd[start][j]!=0) {
                    sq[top] = sd[start][j];
                    //用于记录邻接的城市
                    nextCity = j;
                }
            }
            //当跳出循环的时候，则表示已经找到了该邻接城市
            //将该邻接城市标为已经到过
            flag[nextCity] = 1;
            //输出该邻接城市
            System.out.print((nextCity+1)+"->");
            //将邻接城市作为开头的城市，再次循环，直到所有的城市都被遍历过
            start = nextCity;
            //top++，表示sq的下一个空间用于存储下一段路
            top++;
        }
        System.out.print(firstCity+1);

        System.out.println();
        int sum =0;
        //sq的第五个空间用于存储最后一个地点与出发点的距离
        sq[n-1] = sd[firstCity][start];
        //得出已走过距离的总和
        for(int i = 0;i < n ;i++){
            sum += sq[i];
        }
        System.out.println("使用贪心算法获得的最短距离为：" + sum);
    }
}


